package com.str.graphs;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import com.str.tree.UFTree;

public class Maze {
                 
  private class Cell {
    boolean north;     // is there a wall to north of cell
    boolean east;
    boolean south;
    boolean west;
    boolean flag1;
    boolean flag2;
    
    Cell() {
      north = east = south = west = true;
      flag1 = flag2 = false;	
    }
  }

  private static final int ROWS = 19;       
  private static final int COLS = 38; 
  private static final int SIZE = ROWS * COLS;
  private static final int START_ROW = 0;
  private static final int START_COL = 0;
  private static final int END_ROW = ROWS - 1;
  private static final int END_COL = COLS - 1;
  
  private Cell[][] grid;   
  private boolean done;

  public Maze() {
    grid = new Cell[ROWS][COLS];
    for (int i = 0; i < ROWS; i++)
      for (int j = 0; j < COLS; j++)
        grid[i][j] = new Cell();
    done = false;
  }

  // generate the maze
  public void generateDFS() {
    int i = (int) (Math.random() * ROWS);
    int j = (int) (Math.random() * COLS);
    generateDFS(i, j);
    for (i = 0; i < ROWS; i++)
      for (j = 0; j < COLS; j++)
        grid[i][j].flag1 = false;   
  }
   
  private void generateDFS(int i, int j) {
    grid[i][j].flag1 = true;        // visited

    // while there is an uniflag1 neighbor
    while (i > 0 && !grid[i-1][j].flag1 ||
           j < COLS - 1 && !grid[i][j+1].flag1 ||
           i < ROWS - 1 && !grid[i+1][j].flag1 ||
           j > 0 && !grid[i][j-1].flag1) {

      // pick random neighbor (could use Knuth's trick instead)
      while (true) {
        double r = Math.random();
        if (r < 0.25 && i > 0 && !grid[i-1][j].flag1) {
          grid[i][j].north = grid[i-1][j].south = false;
          generateDFS(i-1, j);
          break;
        }           
        else if (r < 0.50 && j < COLS - 1 && !grid[i][j+1].flag1) {
          grid[i][j].east = grid[i][j+1].west = false;
          generateDFS(i, j+1);
          break;
        }
        else if (r < 0.75 && i < ROWS - 1 && !grid[i+1][j].flag1) {
          grid[i][j].south = grid[i+1][j].north = false;
          generateDFS(i+1, j);
          break;
        }
        else if (r < 1.00 && j > 0 && !grid[i][j-1].flag1) {
          grid[i][j].west = grid[i][j-1].east = false;
          generateDFS(i, j-1);
          break;
        }
      }
    }
  }
  
  public void generatePrim() {	
    int i = (int) (Math.random() * ROWS);
    int j = (int) (Math.random() * COLS);
    generatePrim(i, j);
    for (i = 0; i < ROWS; i++)
      for (j = 0; j < COLS; j++)
        grid[i][j].flag1 = grid[i][j].flag2 = false;   
  }
   
  private void generatePrim(int i, int j) {
  	
  	int[] frontier = new int[SIZE];   
    int count = 0;
    frontier[count++] = i * COLS + j;    
    grid[i][j].flag2 = true;          // FRONTIER
    boolean b = false;         
          
    while (count > 0) {        
      int r1 = (int) (Math.random() * count);    
      i = frontier[r1] / COLS;
      j = frontier[r1] % COLS;  
      grid[i][j].flag1 = true;        // IN
    
      if (i > 0 && !grid[i-1][j].flag2) {
        frontier[count++] = (i - 1) * COLS + j;
        grid[i-1][j].flag2 = true;
      }        
      if (j < COLS - 1 && !grid[i][j+1].flag2) {
        frontier[count++] = i * COLS + j + 1;
        grid[i][j+1].flag2 = true;
      }              
      if (i < ROWS - 1 && !grid[i+1][j].flag2) {
        frontier[count++] = (i + 1) * COLS + j;
        grid[i+1][j].flag2 = true;
      }               
      if (j > 0 && !grid[i][j-1].flag2) {
        frontier[count++] = i * COLS + j - 1;
        grid[i][j-1].flag2 = true;
      }           
      frontier[r1] = frontier[--count];
       
      while (b) {
        double r = Math.random();
        if (r < 0.25 && i > 0 && grid[i-1][j].flag1) {
          grid[i][j].north = grid[i-1][j].south = false;
          break;
        }           
        else if (r < 0.50 && j < COLS - 1 && grid[i][j+1].flag1) {
          grid[i][j].east = grid[i][j+1].west = false;
          break;
        }
        else if (r < 0.75 && i < ROWS - 1 && grid[i+1][j].flag1) {
          grid[i][j].south = grid[i+1][j].north = false;
          break;
        }
        else if (r < 1.00 && j > 0 && grid[i][j-1].flag1) {
          grid[i][j].west = grid[i][j-1].east = false;
          break;
        }
      }
      b = true;          
    } 
  }
  
  void generateKruskal() {
   	UFTree uf = new UFTree(SIZE);
    int k = 1;
      
    while (k < SIZE) {
      int c1 = (int) (Math.random() * SIZE);     	
      int i = c1 / COLS;
      int j = c1 % COLS;    
      int c2;
      double r = Math.random();
	 
	  if (r < 0.25 && i > 0) {  	  
        c2 = (i - 1) * COLS + j;
	    if (uf.differ(c1, c2)) {
	  	  grid[i][j].north = grid[i-1][j].south = false;	
	  	  k++;
	    } 
	  } 
	  else if (r < 0.50 && j < COLS - 1) {
        c2 = i * COLS + j + 1;
	    if (uf.differ(c1, c2)) {
	  	  grid[i][j].east = grid[i][j+1].west = false;	
	  	  k++;
	  	}
	  }  
	  else if (r < 0.75 && i < ROWS - 1) { 
        c2 = (i + 1) * COLS + j;
	  	if (uf.differ(c1, c2)) {
	  	  grid[i][j].south = grid[i+1][j].north = false;	
	  	  k++;
	    }
	  }  
	  else if (r < 1.00 && j > 0) {
        c2 = i * COLS + j - 1;
	  	if (uf.differ(c1, c2)) {
	  	  grid[i][j].west = grid[i][j-1].east = false;	
	  	  k++;
	  	}
	  }  
    }
  }

  // solve the maze using depth first search
  public void solve()
  { solve(START_ROW, START_COL); }   
   
  private void solve(int i, int j) {
      
    if (done || grid[i][j].flag1) return;
    grid[i][j].flag1 = true;      // visited
    grid[i][j].flag2 = true;      // path
      
    // reached upper right
    if (i == END_ROW && j == END_COL) done = true;

    if (!grid[i][j].north) solve(i-1, j);
    if (!grid[i][j].east)  solve(i, j+1);
    if (!grid[i][j].south) solve(i+1, j);
    if (!grid[i][j].west)  solve(i, j-1);

    if (done) return;
    grid[i][j].flag2 = false;
  }

  // display the maze in screen
  public void print() {
    for (int i = 0; i < ROWS; i++) {
      System.out.print("+");	
	  for (int j = 0; j < COLS; j++) {
	    if (grid[i][j].north) System.out.print("-+");
	    else System.out.print(" +");	
	  }
	  System.out.println();	  
	  for (int j = 0; j < COLS; j++) {
	  	if (i == START_ROW && j == START_COL) System.out.print("S");
	    else if (grid[i][j].west) System.out.print("|");
	    else System.out.print(" ");
	    
	    // if (grid[i][j].flag1) { if (grid[i][j].flag2) System.out.print("*"); else System.out.print(".");}
	    if (grid[i][j].flag2) System.out.print("*");
	    else System.out.print(" ");	
	  }
	  if (i == END_ROW)
	  	System.out.print("E");
	  else
	    System.out.print("|");
	  System.out.println();  
	}
    System.out.print("+");	
	for (int j = 0; j < COLS; j++)
	  System.out.print("-+");
	System.out.println("\n");  	
  }	

  // a test client
  public static void main(String args[]) throws IOException {
    BufferedReader stdin = new BufferedReader(
                           new InputStreamReader(System.in));                                                    
                           
  	while (true) {
      System.out.println("-------------------------");
      System.out.println("     1. DFS");
      System.out.println("     2. Prim");    
      System.out.println("     3. Kruskal");
      System.out.print("\tEnter your choice(Enter to quit): ");       
        
      String inputLine = stdin.readLine();      
      if (inputLine.equals(""))
        System.exit(0);  
      int choice = Integer.parseInt(inputLine);
      System.out.println();
      Maze maze = new Maze();

      switch (choice) {      
        case 1 : 
          maze.generateDFS();
          break;

        case 2 :
          maze.generatePrim();
          break;

        case 3 : 
          maze.generateKruskal();
          break;

        default:
          System.out.println("Invalid choice.");
          continue;
      }
      
      maze.print();
      maze.solve();
      maze.print();
    }                
  }
}
